Day22 Leetcode Array系列---- Triangle

本次題目 Triangle by JS

目前，你正在山頂，你累爆了，所以聰明的你會選擇會短的路下山，山坡都有不同的狀況，有的會耗費大量的體力才能通過，有的則可以輕鬆下去，每一個路口都會有兩條叉路，希望以最省體力的方式下山

input = [
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
output = 11

思考路線 1

1. 需要紀錄目前高度
2. 需要紀錄走哪一條路，岔路就用 0 1 2 3 來標示
3. 消耗的體力需要加總
4. 會需要一個迴圈來計算

Coding Time

用 y 來記錄高度，預設是 0 ， ｘ 紀錄走哪條小路，預設是 0 ， total來紀錄消耗的體力

input = [
  [2],
 [3,4],
[6,5,7],
[4,1,8,3]
]
output = 11

function lowPath(ary){
  y = 0
  x = 0
  total = ary[y][x]
  
  return total
}

function expect(a,b){
  console.log(a==b)
}

expect(lowPath(input),output)

迴圈就以到達平底為終止，如果 ary[y+1] 沒有值就代表到平地
每次迴圈都會往山下走一段，所以用 y+=1 來表示高度變化
接著要比較哪一條路比較省體力，用ary[y][x] 與 ary[y][x+1] 來取值，用這種方式是因為觀察過後，發現選擇左邊的路 x 不會變化，選右邊的路 x 會 +1，將體力加總，當到達平地後把總體力消耗回傳

input = [
  [2],
 [3,4],
[6,5,7],
[4,1,8,3]
]
output = 11

function lowPath(ary){
  y = 0
  x = 0
  total = ary[y][x]
  while(!!ary[y+1]){
    y+=1
    if(ary[y][x]<ary[y][x+1]){
      total += ary[y][x]
    }else{
      total +=ary[y][x+1]
      x+=1
    }
  }
  return total
}

function expect(a,b){
  console.log(a==b)
}

expect(lowPath(input),output)

這樣的寫法有可能會遇到錯誤，雖然每一次都在岔路選擇走體力消耗小的路，但是加總起來不一定是體力消耗最小的結果

為了解決這個問題，需要將體力消耗可能的結果都存下，每一次都做比較

function lowPath(ary){
  let y = ary.length - 1
  let result = []
  
  for(let i = 0 ; i < ary.length; i++){
    result.push([])
  }
  
  result[y] = ary[y]

  for(let j = y; j > 0; j-- ){
    for(let k = 0; k < ary[j].length-1; k++){
      item = Math.min( result[j][k] , result[j][k+1] ) + ary[j-1][k]
      result[j-1].push(item)
    }
  }
  console.log(result)
  return result[0][0]
}

function expect(a,b){
 console.log(a==b)
}

expect(lowPath(input),output)

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty